package gold.digger;

import gold.utils.InputUtil;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC2104 {
    public long startExecuteTime = System.currentTimeMillis();


    /*
     * @param 此题目参考了别人代码
     * 这是因为问题情况较为复杂
     * 未来需要再次复习此道题目
     * 奇技淫巧：使用单调栈的炫技操作
     * @return:
     */
    class Solution {
        public long subArrayRanges(int[] nums) {
            int n = nums.length;
            int[] minLeft = new int[n];
            int[] minRight = new int[n];
            int[] maxLeft = new int[n];
            int[] maxRight = new int[n];
            Deque<Integer> minStack = new ArrayDeque<Integer>();
            Deque<Integer> maxStack = new ArrayDeque<Integer>();

            for (int i = 0; i < n; i++) {
                while (!minStack.isEmpty() && nums[minStack.peek()] > nums[i]) {
                    minStack.pop();
                }
                minLeft[i] = minStack.isEmpty() ? -1 : minStack.peek();
                minStack.push(i);

                // 如果 nums[maxStack.peek()] == nums[i], 那么根据定义，
                // nums[maxStack.peek()] 逻辑上小于 nums[i]，因为 maxStack.peek() < i
                while (!maxStack.isEmpty() && nums[maxStack.peek()] <= nums[i]) {
                    maxStack.pop();
                }
                maxLeft[i] = maxStack.isEmpty() ? -1 : maxStack.peek();
                maxStack.push(i);
            }
            minStack.clear();
            maxStack.clear();
            for (int i = n - 1; i >= 0; i--) {
                // 如果 nums[minStack.peek()] == nums[i], 那么根据定义，
                // nums[minStack.peek()] 逻辑上大于 nums[i]，因为 minStack.peek() > i
                while (!minStack.isEmpty() && nums[minStack.peek()] >= nums[i]) {
                    minStack.pop();
                }
                minRight[i] = minStack.isEmpty() ? n : minStack.peek();
                minStack.push(i);

                while (!maxStack.isEmpty() && nums[maxStack.peek()] < nums[i]) {
                    maxStack.pop();
                }
                maxRight[i] = maxStack.isEmpty() ? n : maxStack.peek();
                maxStack.push(i);
            }

            long sumMax = 0, sumMin = 0;
            for (int i = 0; i < n; i++) {
                sumMax += (long) (maxRight[i] - i) * (i - maxLeft[i]) * nums[i];
                sumMin += (long) (minRight[i] - i) * (i - minLeft[i]) * nums[i];
            }
            return sumMax - sumMin;
        }
    }


    public void run() {
        int[] arr = InputUtil.toIntegerArray("[1,2,3]");
        System.out.println(new Solution().toString());
    }

    public static void main(String[] args) throws Exception {
        LC2104 an = new LC2104();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
